package com.wfm.leetcode.editor.cn;
public class PFour40字典序的第K小数字{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9
    public int findKthNumber(int n, int k) {
        int now = 1;
        k--;
        while(k>0){
            int step = getSteps(now,n) ;
//            int step = getSteps(now,now+1,n) ;
            if(step<=k){
                now++;
                k=k-step;
            }else {
                now*=10;
                k--;
            }
        }
        return now;
    }
    // 1 10 11 12  10 12 ->2
    // 1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9
    public int getSteps(int curr, long n) {
        int steps = 0;
        long first = curr;
        long last = curr;
        while (first <= n) {
            steps += Math.min(last, n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }

//    public int countStep(int cur,int next,int n){
//        int step = 0;
//        while (cur<=n){
//            step+=Math.min(n+1,next)-cur;
//            cur*=10;
//            next*=10;
//        }
//        return step;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour40字典序的第K小数字().new Solution();
    }
}